class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        visited = [[False for _ in range(n)] for _ in range(m)]

        def dfs(i,j):
            if i<0 or i>=m or j<0 or j>=n or visited[i][j] or num_count(i, j)>k: return 0

            visited[i][j] = True
            return 1 + dfs(i-1, j) + dfs(i+1, j) + dfs(i, j-1) +dfs(i, j+1)


        def num_count(i, j):
            sum = 0
            while i>0:
                sum+=i%10
                i=i//10

            while j>0:
                sum+=j%10
                j = j//10
            
            return sum
        return dfs(0,0)


if __name__ == '__main__':
    Solution().movingCount(1,2,1)
